#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    string sortString(string s)
    {
        vector<int> ans(26, 0);
        for (char c : s)
        {
            ans[c - 'a']++;
        }
        string str = "";
        auto checkString = [](vector<int> res) -> bool
        {
            for (int i = 0; i < 26; i++)
            {
                if (res[i] > 0)
                    return true;
            }
            return false;
        };
        while (checkString(ans))
        {
            // stop 2
            for (int i = 0; i < 26; i++)
            {
                if (ans[i] > 0)
                {
                    str.push_back(i + 'a');
                    ans[i]--;
                }
            }
            // step 5
            for (int i = 25; i >= 0; i--)
            {
                if (ans[i] > 0)
                {
                    str.push_back(i + 'a');
                    ans[i]--;
                }
            }
        }
        return str;
    }

    string sortString_2(string s)
    {
        string res = "";
        vector<int> hash(26);
        int l = 0;
        for (auto &c : s)
        {
            hash[c - 'a']++;
        }
        while (res.size() < s.size())
        {
            while (l < 26)
            {
                while (l < 26 && hash[l] == 0)
                    l++;
                if (l < 26)
                {
                    hash[l]--;
                    res += (l + 'a');
                    l++;
                }
            }
            l--;
            while (l >= 0)
            {
                while (l >= 0 && hash[l] == 0)
                    l--;
                if (l >= 0)
                {
                    hash[l]--;
                    res += (l + 'a');
                    l--;
                }
            }
            l++;
        }
        return res;
    }

    string sortString_3(string s)
    {
        vector<int> num(26);
        for (char &ch : s)
        {
            num[ch - 'a']++;
        }

        string ret;
        while (ret.length() < s.length())
        {
            for (int i = 0; i < 26; i++)
            {
                if (num[i])
                {
                    ret.push_back(i + 'a');
                    num[i]--;
                }
            }
            for (int i = 25; i >= 0; i--)
            {
                if (num[i])
                {
                    ret.push_back(i + 'a');
                    num[i]--;
                }
            }
        }
        return ret;
    }
};
int main()
{
    Solution s;
    string str = "aaaabbbbcccc";
    cout << s.sortString_2(str) << endl;
    system("pause");
    return 0;
}
